package sysu.el.graph.undi.algor;

import sysu.el.array.BoolArray;
import sysu.el.array.algors.Sig;
import sysu.el.array.ints.ArrQueueInt;
import sysu.el.graph.undi.UndiGTAdjList;

public class WidthCalculation {
	public UndiGTAdjList adj;
	public BoolArray isVisited;
	public int[] cache;
	public int[] fa;
	public ArrQueueInt queue;
	public WidthCalculation(UndiGTAdjList adj){
		this.adj = adj;
		this.isVisited = new BoolArray(adj.getNodeNum());
		this.fa = new int[adj.getNodeNum()];
		this.queue = new ArrQueueInt(adj.getNodeNum());
	}
	public void reset(){
		this.isVisited.reset();
		this.cache = new int[adj.getNodeNum()];
		this.queue.reset();
	}
	
	public int cal(int root){
		reset();
		isVisited.setVisited(root);
		queue.add(root);
		fa[root] = -1;
		while (queue.isEmpty()==false){
			int h = queue.forward();
			int[] nodes = adj.getList(h);
			for (int i=0; i<adj.getDegree(h); ++i){
				int curnode = nodes[i];
				if (isVisited.isVisited(curnode)) continue;
				isVisited.setVisited(curnode);
				fa[curnode] = h;
				queue.add(curnode);
			}
		}
		int nodes[] = queue.elements();
		System.out.println(Sig.mkString(nodes, "\t"));
		for (int i=adj.getNodeNum()-1; i>=1; --i){
			int curnode = nodes[i];
			if (cache[curnode] == 0) cache[curnode] = 1;
			cache[fa[curnode]] += cache[curnode];
		}
		return cache[root];
	}
	
	public float x[], y[], r[];
	public void layoutSpand(int root){
		cal(root);
		int nodes[] = queue.elements();
		x = new float[adj.getNodeNum()];
		y = new float[adj.getNodeNum()];
		r = new float[adj.getNodeNum()];
		float start[] = new float[adj.getNodeNum()];
		float end[] = new float[adj.getNodeNum()];
		start[root] = 0;
		end[root] = (float)Math.PI;
		r[root] = 0;
		for (int i=0; i<adj.getNodeNum(); ++i){
			int curnode = nodes[i];
			
			float sep = (end[curnode] - start[curnode]) / cache[curnode];
			float startr = start[curnode];
			
			for (int j=0; j<adj.getNodeNum(); ++j){
				if (fa[j] != curnode) continue;
				r[j] = r[curnode] + 1;
				float endr = startr+(sep * cache[j]);
				start[j] = startr;
				end[j] = endr;
				startr = endr;
				System.out.println("Root\t" + j + "\t" + (start[j]+end[j])/2.0f);
				x[j] = (float) (r[j] * Math.cos((start[j]+end[j])/2.0f));
				y[j] = (float) (r[j] * Math.sin((start[j]+end[j])/2.0f));
			}
			
			
		}
	}
	
	public static void main(String[] args) {
		UndiGTAdjList graph = new UndiGTAdjList(9);
		int data[] = new int[]{0, 1, 0, 2, 1, 3, 1, 4, 2, 5, 2, 6, 3, 7, 3, 8, 4, 8};
		for (int i=0; i<data.length >> 1; i++){
			graph.addEdge(data[i<<1], data[(i<<1)+1]);
		}
		
		WidthCalculation w = new WidthCalculation(graph);
		System.out.println("Width:\t" + w.cal(0));
		System.out.println(Sig.mkString(w.cache, "\t"));
		w.layoutSpand(0);
		System.out.println(Sig.mkString(w.x, "\t"));
		System.out.println(Sig.mkString(w.y, "\t"));
	}
}
